#!/usr/bin/python
# -*- coding: utf8 -*-

from sets import Set


def vacio(s):
    '''Determina si un contenedor es vacío'''
    return len(s) == 0


################################
# Excepciones                  #
################################

class GrammarError(Exception):
    def __init__(self, mensaje, nodo):
        self.mensaje = mensaje
        self.nodo = nodo
    
    def __str__(self):
        s = ""
        if not (self.nodo is None):
            s += "Error en "+ str(self.nodo) + "\n"
        s += self.mensaje
        return s


################################
# Clase Raíz de Nodos          #
################################

class NodoGramatica:
    def anulable(self, parser):
        '''Devuelve si este NodoGramatica es anulable'''
        raise NotImplementedError

    def primeros(self, parser):
        '''Devuelve primeros() de este NodoGramatica'''
        raise NotImplementedError

    def agregar_siguientes(self, parser, c):
        '''Recalcula los elementos siguientes() de los nodos hijos y
           de este NodoGramatica agregando los elementos de c donde
           corresponda'''
        raise NotImplementedError
            
    def siguientes(self, parser):
        '''Devuelve siguientes() de este NodoGramatica'''
        return parser.ts[self]

    def directores(self, parser):
        '''Devuelve los símbolos directores de este NodoGramatica'''
        raise NotImplementedError

    def generarCodigo(self, parser, buf):
        '''Devuelve el código correspondiente al parsing de este
           símbolo para generar el parser'''
        raise NotImplementedError

    def preOrder(self):
        '''Devuelve la lista preorder de todos los elementos
           del árbol de símbolos que comienza en este NodoGramatica'''
        raise NotImplementedError

    def aplastar(self):
        '''Devuelve un conjunto con todos los elementos del árbol
           de símbolos que comienza en este NodoGramatica'''
        return Set(self.preOrder())
        
    def inutil(self, parser):
        '''Devuelve si este NodoGramatica es inútil'''
        raise NotImplementedError
    
    # FIXME: no es lo más lindo esto
    def __hash__(self):
        return hash(str(self))

    def __eq__(self, otro):
        return self is otro

    def __repr__(self):
        return str(self)
        


################################
# Símbolos                     #
################################

class Simbolo(NodoGramatica):
    def __init__(self, simbolo):
        self.simbolo = simbolo
        self.precedencia = 4

    def preOrder(self):
        return [self]

    def __str__(self):
        return self.simbolo
    
    def perteneceSubArbol(self,nodo):
        return self == nodo
    
    def generarDot(self):
        s = str(id(self)) + '[label="'+ str(self) +'"];'
        return s
    

class SimboloLambda(NodoGramatica):
    def __init__(self):
        self.precedencia = 4
    
    def perteneceSubArbol(self,nodo):
        return self == nodo
    
    def generarDot(self):
        s = str(id(self)) + '[label="'+ str(self) +'"];'
        return s
    
    def preOrder(self):
        return [self]
    
    def anulable(self, parser):
        return True

    def primeros(self, parser):
        return Set()
        
    def agregar_siguientes(self, parser, s):
        parser.ts[self] = parser.ts[self].union(s)
    
    def directores(self, parser):
        if parser.td[self] is None:
            parser.td[self] = self.siguientes(parser)
        return parser.td[self]

    def inutil(self, parser):
        return False
    
    def generarCodigo(self, parser, buf):
        buf.linea("pass")
            
    def __str__(self):
        return '_'

class SimboloTerminal(Simbolo):
    def anulable(self, parser):
        return False

    def primeros(self, parser):
        return Set([self.simbolo])

    def agregar_siguientes(self, parser, s):
        parser.ts[self] = parser.ts[self].union(s)
    
    def directores(self, parser):
        if parser.td[self] is None:
            parser.td[self] = Set([self.simbolo])
            
        return parser.td[self]

    def inutil(self, parser):
        return False
        
    def generarCodigo(self, parser, buf):
         buf.linea("match('%s')" % self.simbolo)
         
    def __str__(self):
            return self.simbolo


class SimboloNoTerminal(Simbolo):
    def anulable(self, parser):
        return parser.ta[self.simbolo]

    def primeros(self, parser):
        return parser.tp[self.simbolo]

    def agregar_siguientes(self, parser, s):
        parser.ts[self] = parser.ts[self].union(s)

    def directores(self, parser):
        if parser.td[self] is None:
            if self.anulable(parser):
                if vacio(self.primeros(parser).intersection(self.siguientes(parser))):
                    parser.td[self] = self.primeros(parser).union(self.siguientes(parser))
                else:                  
                    raise GrammarError(self._mensajeDeErrorNoDisjuntos(parser),self)
            else:
                parser.td[self] = self.primeros(parser)

        return parser.td[self]

    def _mensajeDeErrorNoDisjuntos(self, parser):
        mensaje = ("El no terminal %s es anulable\n" + \
                   "pero sus primeros no son disjuntos con sus siguientes.\n" + \
                   "Sus primeros son: \n" + \
                   "%s\n" + \
                   "Sus siguientes son: \n" + \
                   "%s")  % (self.simbolo, self.primeros(parser), self.siguientes(parser))
        return mensaje
    
    def inutil(self,parser):
        return parser.ti[self.simbolo]
        
    def generarCodigo(self, parser, buf):
        buf.linea("noterm_%s()" % self.simbolo)

    def __eq__(self, otro):
        if isinstance(otro, SimboloNoTerminal):
            return self.simbolo == otro.simbolo
        else:
            return False



################################
# Operandos Unarios            #
################################

class OperandoUnario(NodoGramatica):
    def __init__(self, hijo):
        self.hijo = hijo
        self.precedencia = 3
    
    def preOrder(self):
        return [self] + self.hijo.preOrder()

    def directores(self, parser):
        if parser.td[self] is None:
            if self.hijo.anulable(parser):
                raise GrammarError(self._mensajeDeErrorHijoAnulable(parser),self)
            if vacio(self.primeros(parser).intersection(self.siguientes(parser))):
                parser.td[self] = self.primeros(parser).union(self.siguientes(parser))
            else:
                raise GrammarError(self._mensajeDeErrorNoDisjuntos(parser),self)
        return parser.td[self]
        
    def _mensajeDeErrorHijoAnulable(self, parser):
        return "El hijo de un operando unario no puede ser anulable!"
    
    def _mensajeDeErrorNoDisjuntos(self, parser):
        '''Devuelve un mensaje de error generico'''
        mensaje = ("Los primeros de un nodo anulable deben ser disjuntos con sus siguientes\n"  + \
                   "Sus primeros son:\n" + \
                   "%s\n"+\
                   "Sus siguientes son:\n" + \
                   "%s") % \
                   (self.primeros(parser), self.siguientes(parser))
        return mensaje
    
    def perteneceSubArbol(self,nodo):
        return self == nodo or self.hijo.perteneceSubArbol(nodo)
        
    def generarDot(self):
        s = str(id(self))+'[label="'+str(self)+'"];'
        s += str(id(self))+"->" + str(id(self.hijo)) + ";\n"
        s += self.hijo.generarDot()
        return s


class OperandoPreg(OperandoUnario):
    def anulable(self, parser):
        return True

    def primeros(self, parser):
        return self.hijo.primeros(parser)
    
    def agregar_siguientes(self, parser, s):
        parser.ts[self] = parser.ts[self].union(s)
        self.hijo.agregar_siguientes(parser, s)

    def inutil(self,parser):
        return False 
    
    def generarCodigo(self, parser, buf):
        dirs = self.hijo.directores(parser)
        buf.linea("if tc() in %s:" % dirs)
        buf.indentar()
        self.hijo.generarCodigo(parser, buf)
        buf.desindentar()

    def __str__(self):
        if self.precedencia <= self.hijo.precedencia:
            return str(self.hijo)+"?"
        else:
            return "(%s)?" % self.hijo
        
    def generarDot(self):
        s = str(id(self))+'[label="'+" ? "+'"];'
        s += str(id(self))+"->" + str(id(self.hijo)) + ";\n"
        s += self.hijo.generarDot()
        return s


class OperandoMas(OperandoUnario):
    def anulable(self, parser):
        return self.hijo.anulable(parser)

    def primeros(self, parser):
        return self.hijo.primeros(parser)

    def agregar_siguientes(self, parser, s):
        parser.ts[self] = parser.ts[self].union(s)
        self.hijo.agregar_siguientes(parser, self.hijo.primeros(parser))
        self.hijo.agregar_siguientes(parser, s)

    def directores(self, parser):
        if parser.td[self] is None:
            if self.hijo.anulable(parser):
                raise GrammarError(self._mensajeDeErrorHijoAnulable(parser),self)
            elif not vacio(self.primeros(parser).intersection(self.siguientes(parser))) :
                 raise GrammarError(self._mensajeDeErrorNoDisjuntos(parser),self)  
            else:
                parser.td[self] = self.hijo.primeros(parser)

        return parser.td[self]

    def _mensajeDeErrorNoDisjuntos(self, parser):
        mensaje = ("Los primeros de un nodo + deben ser disjuntos con sus siguientes\n"  + \
                   "Sus primeros son:\n" + \
                   "%s\n"+\
                   "Sus siguientes son:\n" + \
                   "%s") % \
                   (self.primeros(parser), self.siguientes(parser))
        return mensaje
    
    def inutil(self, parser):
        return self.hijo.inutil(parser)
    
    def generarCodigo(self, parser, buf):
        dirs = self.hijo.directores(parser)
        self.hijo.generarCodigo(parser, buf)
        buf.linea("while tc() in %s:" % dirs)
        buf.indentar()
        self.hijo.generarCodigo(parser, buf)
        buf.desindentar()

    def __str__(self):
         if  self.precedencia <= self.hijo.precedencia:
             return str(self.hijo)+"+"
         else:
             return "(%s)+" % self.hijo

    def generarDot(self):
        s = str(id(self))+'[label="'+" + "+'"];'
        s += str(id(self))+"->" + str(id(self.hijo)) + ";\n"
        s += self.hijo.generarDot()
        return s

class OperandoEstrella(OperandoUnario):
    def anulable(self, parser):
        return True

    def primeros(self, parser):
        return self.hijo.primeros(parser)
    
    def agregar_siguientes(self, parser, s):
        parser.ts[self] = parser.ts[self].union(s)
        self.hijo.agregar_siguientes(parser, self.hijo.primeros(parser))
        self.hijo.agregar_siguientes(parser, s)

    def inutil(self,parser):
        return False
    
    def generarCodigo(self, parser, buf):
        dirs = self.hijo.directores(parser)
        buf.linea("while tc() in %s:" % dirs)
        buf.indentar()
        self.hijo.generarCodigo(parser, buf)
        buf.desindentar()

    def __str__(self):
        if self.precedencia <= self.hijo.precedencia:
            return str(self.hijo)+"*"
        else:
            return "(%s)*" % self.hijo
        
    def generarDot(self):
        s = str(id(self))+'[label="'+" * "+'"];'
        s += str(id(self))+"->" + str(id(self.hijo)) + ";\n"
        s += self.hijo.generarDot()
        return s


################################
# Operandos Binarios           #
################################

class OperandoBinario(NodoGramatica):
    def __init__(self, izq, der):
        self.izq = izq
        self.der = der

    def preOrder(self):
        return [self] + self.izq.preOrder() + self.der.preOrder()
        
    
    def perteneceSubArbol(self,nodo):
        return self == nodo or \
                     self.izq.perteneceSubArbol(nodo) or \
                     self.der.perteneceSubArbol(nodo)
    
    def generarDot(self):
        s = str(id(self))+'[label="'+str(self)+'"];\n'
        s += str(id(self))+"->" + str(id(self.izq)) + ";\n"
        s += str(id(self))+"->" + str(id(self.der)) + ";\n"
        s += self.izq.generarDot()
        s += self.der.generarDot()
        return s


class OperandoConcat(OperandoBinario):
    def __init__(self, izq, der):
        self.izq = izq
        self.der = der
        self.precedencia = 2
    
    def anulable(self, parser):
        return self.izq.anulable(parser) and self.der.anulable(parser)
    
    def primeros(self, parser):
        if self.izq.anulable(parser):
            return self.izq.primeros(parser).union(self.der.primeros(parser))
        else:
            return self.izq.primeros(parser)

    def agregar_siguientes(self, parser, s):
        parser.ts[self] = parser.ts[self].union(s)
        
        self.izq.agregar_siguientes(parser, self.der.primeros(parser))

        self.der.agregar_siguientes(parser, s)
        if self.der.anulable(parser):
            self.izq.agregar_siguientes(parser, s)

    def directores(self, parser):
        if parser.td[self] is None:
            if self.izq.anulable(parser):
                
                if vacio(self.izq.primeros(parser).intersection(self.der.primeros(parser))):
                    
                    if self.der.anulable(parser):
                        
                        if vacio((self.izq.primeros(parser).union(self.der.primeros(parser))).intersection(self.siguientes(parser))) :
                            parser.td[self] = self.izq.primeros(parser).union(self.der.primeros(parser)).union(self.siguientes(parser))
                        else:
                            raise GrammarError(self._mensajeDeErrorNoDisjuntos(parser), self)
                    
                    else:
                        parser.td[self] = self.izq.primeros(parser).union(self.der.primeros(parser))
                       
                else:
                    raise GrammarError(self._mensajeDeErrorHijos(parser), self)
            
            else:
                    parser.td[self] = self.izq.directores(parser)

        return parser.td[self]
    
    def _mensajeDeErrorHijos(self, parser):
        mensaje = ("El nodo izquierdo de una concatenación es anulable\n"+\
                   "pero sus primeros no son disjuntos con los de su hermano.\n"+\
                   "Los primeros de '%s' son:\n"+\
                   "%s\n"+\
                   "Los primeros de '%s' son:\n"+\
                   "%s") % (self.izq, self.izq.primeros(parser), self.der, self.der.primeros(parser))
        return mensaje
    
    def _mensajeDeErrorNoDisjuntos(self, parser):
        mensaje = ("La concatenacion %s es anulable\n" + \
                   "pero sus primeros no son disjuntos con sus siguientes.\n" + \
                   "Sus primeros son: \n" + \
                   "%s\n" + \
                   "Sus siguientes son: \n" + \
                   "%s")  % (str(self), self.primeros(parser), self.siguientes(parser))
        return mensaje
    
    def inutil(self, parser):
        return self.izq.inutil(parser) or self.der.inutil(parser)
    
    def generarCodigo(self, parser, buf):
        self.izq.generarCodigo(parser, buf)
        self.der.generarCodigo(parser, buf)
        

    def __str__(self):
        if self.izq.precedencia < self.precedencia:
            strIzq = "(%s)" % self.izq
        else:
            strIzq = str(self.izq)
        if self.der.precedencia < self.precedencia:
            strDer = "(%s)" % self.der
        else:
            strDer = str(self.der)
        return "%s%s" % (strIzq, strDer)
        
    def generarDot(self):
        s = str(id(self))+'[label="'+" . "+'"];\n'
        s += str(id(self))+"->" + str(id(self.izq)) + ";\n"
        s += str(id(self))+"->" + str(id(self.der)) + ";\n"
        s += self.izq.generarDot()
        s += self.der.generarDot()
        return s

   

class OperandoUnion(OperandoBinario):
    def __init__(self, izq, der):
        self.izq = izq
        self.der = der
        self.precedencia = 1
        
    def anulable(self, parser):
        return self.izq.anulable(parser) or self.der.anulable(parser)

    def primeros(self, parser):
        return self.izq.primeros(parser).union(self.der.primeros(parser))

    def agregar_siguientes(self, parser, s):
        parser.ts[self] = parser.ts[self].union(s)
        self.izq.agregar_siguientes(parser, s)
        self.der.agregar_siguientes(parser, s)

    def directores(self, parser):
        if parser.td[self] is None:
            if self.izq.anulable(parser) and self.der.anulable(parser):
                raise GrammarError(self._mensajeDeErrorHijosAnulables(parser), self)
            else:
                dirIzq = self.izq.directores(parser)
                dirDer = self.der.directores(parser)
                if vacio(dirIzq.intersection(dirDer)):
                    parser.td[self] = dirIzq.union(dirDer)
                else:
                    raise GrammarError(self._mensajeDeErrorHijos(parser), self)

        return parser.td[self]
        
    def _mensajeDeErrorHijos(self, parser):
        mensaje = ("Los directores de los nodos de una unión deben ser disjuntos,\n"+\
                   "pero los directores de '%s' y '%s' poseen estos elementos en común:\n"+\
                   "%s") % (self.izq, self.der, self.izq.directores(parser).intersection(self.der.directores(parser)))
        return mensaje
 
    def inutil(self, parser):
        return self.izq.inutil(parser) and self.der.inutil(parser)
    
    def generarCodigo(self, parser, buf):
        dirs_izq = self.izq.directores(parser)
        dirs_der = self.der.directores(parser)
        buf.linea("if tc() in %s:" % dirs_izq)
        buf.indentar()
        self.izq.generarCodigo(parser, buf)
        buf.desindentar()
        buf.linea("elif tc() in %s:" % dirs_der)
        buf.indentar()
        self.der.generarCodigo(parser, buf)
        buf.desindentar()
        buf.linea("else:")
        buf.indentar()
        buf.linea("raise ParseError(%s)" % dirs_der.union(dirs_izq))
        buf.desindentar()
        

    def __str__(self):
        return "%s|%s" % (self.izq, self.der)
        
    def generarDot(self):
        s = str(id(self))+'[label="'+" | "+'"];\n'
        s += str(id(self))+"->" + str(id(self.izq)) + ";\n"
        s += str(id(self))+"->" + str(id(self.der)) + ";\n"
        s += self.izq.generarDot()
        s += self.der.generarDot()
        return s
    
    def _mensajeDeErrorHijosAnulables(self, parser):
        return "Los dos elementos de una union no pueden ser anulables!\n"


